package th.retrofit.lib;

public class Solution99 {
    private boolean flag = false;
    TreeNode node1 = null;
    TreeNode node2 = null;
    TreeNode preNode = null;
    public void recoverTree(TreeNode root) {
        findInvalidNode(root);
        int temp = node1.val;
        node1.val = node2.val;
        node2.val = temp;
    }

    private void findInvalidNode(TreeNode root) {
        if (root == null) return;
        findInvalidNode(root.left);
        if (preNode != null && root.val < preNode.val) {
            node2 = root;
            if (node1 == null) {
                node1 = preNode;
            } else {
                flag = true;
            }
        }
        if (flag) return;
        preNode = root;
        findInvalidNode(root.right);
    }

    public static void main(String[] args) {
        TreeNode root = TreeNode.array2Tree(1,3,null,null,2);
        new Solution99().recoverTree(root);
        System.out.println(root.toString());
    }
}
